#include<iostream>

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};


class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head) return head;
        // 增加虚拟头部
        ListNode voidHead(-1);

        voidHead.next = head;
        // 迭代归并
        int step = 1;
        int cnt = 0;
        ListNode *ptr = head, *a, *b;
        while (ptr) {
            cnt += 1;
            ptr = ptr->next;
        }
        while (step < cnt) {
            ptr = &voidHead;
            while (ptr->next) {
                a = ptr->next;
                b = ptr->next;
                for (int i = 0; i < step-1 && a->next; i++) a = a->next;
                if (!a->next) break;
                b = a->next;
                for (int i = 0; i < step-1 && b->next; i++) b = b->next;
                auto ptrNext = ptr->next;
                // 待归并的链表头，其余关系删除
                auto nextPtr = b->next;
                auto aNext = a->next;
                a->next = nullptr;
                b->next = nullptr;
                ptr->next = mergeSort(ptrNext, aNext);
                auto tail = ptr->next;
                while (tail->next) tail = tail->next;
                tail->next = nextPtr;
                ptr = tail;
            }
            step *= 2;
        }

        return voidHead.next;

        
    }

    ListNode* mergeSort(ListNode* a, ListNode* b) {
        if (!b) return a;
        if (!a) return b;
        // 头部值排序
        ListNode head(-1);
        ListNode* ptr = &head;
        while (a && b) {
            if (a->val <= b->val) {
                ptr->next = a;
                a = a->next;
            }
            else {
                ptr->next = b;
                b = b->next;
            }
            ptr = ptr->next;
        }
        if (a) ptr->next = a;
        if (b) ptr->next = b;
        return head.next;
    }

    
};

int main() {
    int n;
    ListNode head(-1);
    ListNode* ptr = &head;
    while (std::cin >> n) {
        std::cout << n << " ";
        ptr->next = new ListNode(n);
        ptr = ptr->next;
    }
    std::cout << "\n";
    head.next = Solution().sortList(head.next);
    ptr = head.next;
    while (ptr) {
        std::cout << ptr->val << " ->";
        ptr = ptr->next;
    }
    ptr = head.next;
    auto a = ptr;
    while (ptr) {
        a = ptr->next;
        delete ptr;
    }
    return 0;
}